package Algorithm_study.recursion_algorithm;

import java.util.Scanner;

/**
 * 用于求解整数划分问题的代码！
 * 问题描述：
 *      将正整数 n 划分为一系列正整数之和，称为是正整数 n 的一次划分；
 *      正整数 n 的不同划分个数称为正整数 n 的划分数。
 * @author YiWen Wan
 */
public class IntegerDivision {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入你想进行划分的正整数：");
        int n = scanner.nextInt();
        System.out.println("输入允许的最大加数：");
        int m = scanner.nextInt();
        System.out.println("数据"+n+"在最大加数不超过"+m+"的情况下的划分数为："+Count(n,m));
        scanner.close();
    }

    /**
     * 用于计算求解正整数的划分数！
     * @param n：待划分数据。
     * @param m：允许的最大加数。
     * @return：返回划分数的值。
     */
    public static int Count(int n,int m){
        if (n<1||m<1)
            return 0;
        if (n==1||m==1)
            return 1;
        if (n<m)
            return Count(n,n);
        if (n==m)
            return 1+Count(n,m-1);
        return Count(n,m-1)+Count(n-m,m);
    }
}
